Quantum algorithms are global random searching algorithms based on the principles, laws and effects of quantum mechanics. They are used for controlling a process or for processing data in a database, and more specifically, for controlling a process that may include search-of-minima intelligent operations.
In a quantum search, each design variable is represented by a finite linear superposition of initial states, with a sequence of elementary unitary steps manipulating the initial quantum state |i> (for the input) such that a measurement of the final state of the system yields the correct output. Usually, three principle operators, i.e., linear superposition (coherent states), entanglement and interference, are used in the quantum search algorithm.
For a better understanding, a brief description of quantum search algorithms is provided. The problems solved by quantum algorithms may be stated as follows:
InputA function f: {0, 1}n →{0, 1}mProblemFind a certain property of fThe structure of a quantum algorithm is outlined by a high level representation in the schematic diagram of FIG. 1.
The input of a quantum algorithm is always a function f from binary strings into binary strings. This function is represented as a map table, which defines for every string its image. Function f is first encoded into a unitary matrix operator UF depending on f properties. This operator calculates f when its input and output strings are encoded into canonical basis vectors of a Complex Hilbert Space: UF maps the vector code of every string into the vector code of its image by f.
                                                                 ⁢                      BOX            ⁢                                                  ⁢            1            ⁢                          :                        ⁢                                                  ⁢            UNITARY            ⁢                                                  ⁢            MATRIX            ⁢                                                  ⁢                          U              F                                                                                A            ⁢                                                  ⁢            squared            ⁢                                                  ⁢            matrix            ⁢                                                  ⁢                          U              F                        ⁢                                                  ⁢            on            ⁢                                                  ⁢            the            ⁢                                                  ⁢            complex            ⁢                                                  ⁢            field            ⁢                                                  ⁢            is            ⁢                                                  ⁢            unitary                    ⁢                                                                              if          ⁢                                          ⁢          its          ⁢                                          ⁢          inverse          ⁢                                          ⁢          matrix          ⁢                                          ⁢          coincides          ⁢                                          ⁢          with          ⁢                                          ⁢          its          ⁢                                          ⁢          conjugate          ⁢                                          ⁢          transpose          ⁢                      :                                                                                        ⁢                                    U              F                              -                1                                      =                          U              F              =                                                                    A          ⁢                                          ⁢          unitary          ⁢                                          ⁢          matrix          ⁢                                          ⁢          is          ⁢                                          ⁢          always          ⁢                                          ⁢          reversible          ⁢                                          ⁢          and          ⁢                                          ⁢          preserves          ⁢                                          ⁢          the          ⁢                                          ⁢          norm                                              of          ⁢                                          ⁢                      vectors            .                              
When the matrix operator UF has been generated, it is embedded into a quantum gate G, a unitary matrix whose structure depends on the form of matrix UF and on the problem to be solved. The quantum gate is the core of a quantum algorithm. In every quantum algorithm, the quantum gate acts on an initial canonical basis vector (the same vector can always be chosen) to generate a complex linear combination (called a superposition) of basis vectors as the output. The superposition contains all the information to answer the initial problem.
After the superposition has been created, a measurement takes place to extract this information. In quantum mechanics, measurement is a non-deterministic operation that produces as output only one of the basis vectors in the superposition. The probability of every basis vector being the output of a measurement depends on its complex coefficient (probability amplitude) in entering a complex linear combination.
The segmental action of the quantum gate and of the measurement forms the quantum block. The quantum block is repeated k times to produce a collection of k basis vectors. In measuring a non-deterministic operation, these basic vectors would not be necessarily identical and each one of them will encode a piece of the information needed to solve the problem. The last part of the algorithm includes interpretation of the collected basis vectors to get the right answer for the initial problem with a certain probability.
The behavior of the encoder block is described in the detailed schematic diagram of FIG. 2. Function f is encoded into matrix UF in three steps.
Step 1: The map table of function f:{0,1}n→{0,1}m is transformed into the map table of the injective function F:{0,1}n+m→{0,1}n+m such that:F(x0, . . . , xn−1, y0, . . . , ym−1)=(x0, . . . , xn−1, f(x0, . . . , xn−1)⊕(y0, . . . , ym−1))  (1)
                                                                 ⁢                                    BOX              ⁢                                                          ⁢              2              ⁢                              :                            ⁢                                                          ⁢              XOR              ⁢                                                          ⁢              OPERATOR                        ⁢                                                  ⊕                                                                    The            ⁢                                                  ⁢            XOR            ⁢                                                  ⁢            operator            ⁢                                                  ⁢            between            ⁢                                                  ⁢            two            ⁢                                                  ⁢            binary            ⁢                                                  ⁢            strings            ⁢                                                  ⁢            p            ⁢                                                  ⁢            and            ⁢                                                  ⁢            q                    ⁢                                                                              of          ⁢                                          ⁢          length          ⁢                                          ⁢          m          ⁢                                          ⁢          is          ⁢                                          ⁢          a          ⁢                                          ⁢          string          ⁢                                          ⁢          s          ⁢                                          ⁢          of          ⁢                                          ⁢          length          ⁢                                          ⁢          m          ⁢                                          ⁢          such          ⁢                                          ⁢          that          ⁢                                          ⁢          the          ⁢                                          ⁢          i          ⁢                      -                    ⁢          th          ⁢                                          ⁢          digit                                              of          ⁢                                          ⁢          s          ⁢                                          ⁢          is          ⁢                                          ⁢          calculated          ⁢                                          ⁢          as          ⁢                                          ⁢          the          ⁢                                          ⁢          exclusive          ⁢                                          ⁢          OR          ⁢                                          ⁢          between          ⁢                                          ⁢          the          ⁢                                          ⁢          i          ⁢                      -                    ⁢          th          ⁢                                          ⁢          digits                                              of          ⁢                                          ⁢          p          ⁢                                          ⁢          and          ⁢                                          ⁢          q          ⁢                      :                                                                                        ⁢                      p            =                          (                                                p                  0                                ,                …                ⁢                                                                  ,                                  p                                      n                    -                    1                                                              )                                                                                                    ⁢                      q            =                          (                                                q                  0                                ,                …                ⁢                                                                  ,                                  q                                      n                    -                    1                                                              )                                                                                s            =                                          p                ⊕                q                            =                              (                                                                            (                                                                        p                          0                                                +                                                  q                          0                                                                    )                                        ⁢                                                                                  ⁢                    mod                    ⁢                                                                                  ⁢                    2                                    ,                  …                  ⁢                                                                          ,                                                            (                                                                        p                                                      n                            -                            1                                                                          +                                                  q                                                      n                            -                            1                                                                                              )                                        ⁢                                                                                  ⁢                    mod                    ⁢                                                                                  ⁢                    2                                                  )                                              )                    
The need to deal with an injective function comes from the requirement that UF is unitary. A unitary operator is reversible, so it cannot map two different inputs in the same output. Given that UF is the matrix representation of F, F is supposed to be infective. If the matrix representation of function f is directly used, a non-unitary matrix could be obtained since f could be non-injective. Injectivity is thus fulfilled by increasing the number of bits and considering function F instead of function f. Function f can always be calculated from F by putting (y0, . . . , ym−1)=(0, . . . , 0) in the input string and reading the last m values of the output string.
Step 2: Function F map table is transformed into UF map table, following the following constraint:∀sε{0,1}n+m:UF[τ(s)]=τ[F(s)]  (2)The code map τ:{0,1}n+m→c2n+m(c2n+m is the target Complex Hilbert Space) is such that:
                                                                                          τ                  ⁡                                      (                    0                    )                                                  =                                                      (                                                                                            1                                                                                                                      0                                                                                      )                                    =                                      |                    0                                                              〉                        ⁢                                                  ⁢                          τ              ⁡                              (                1                )                                              =                                    (                                                                    0                                                                                        1                                                              )                        =                          |              1                                      〉                            (        3        )                                                      τ            ⁡                          (                                                x                  0                                ,                …                ⁢                                                                  ,                                  x                                      n                    +                    m                    -                    1                                                              )                                =                                                    τ                ⁡                                  (                                      x                    0                                    )                                            ⊗              …              ⊗                              τ                ⁡                                  (                                      x                                          n                      +                      m                      -                      1                                                        )                                                      =                          |                                                x                  0                                ⁢                …                ⁢                                                                  ⁢                                                      x                                          n                      +                      m                      -                      1                                                                                                                                                                  〉                                        
  BOX  ⁢          ⁢  3  ⁢      :    ⁢          ⁢  VECTOR  ⁢          ⁢  TENSOR  ⁢          ⁢      PRODUCT    ⊗  The tensor product between two vectors of dimensionsh and k is a tensor product of dimension hk, suchthat:                                           ❘            x                    〉                ⊗            |      y        〉    =                    (                                                            x                1                                                                        …                                                                          x                h                                                    )            ⊗              (                                                            y                1                                                                        …                                                                          y                k                                                    )              =                  (                                                                              x                  1                                ⁢                                  y                  1                                                                                        …                                                                                            x                  1                                ⁢                                  y                  k                                                                                        …                                                                                            x                  h                                ⁢                                  y                  1                                                                                        …                                                                                            x                  h                                ⁢                                  y                  k                                                                    )            ⇒                                                                  Physical                ⁢                                                                  ⁢                interpretation                ⁢                                  :                                            _                                                                          If a component of a complexvector is interpreted as theprobability amplitude of asystem being in a given state(indexed by the componentnumber, the tensor product between two vectors describesthe joing probability amplitudeof two systems being in a joint state.                                          